<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <title>插入排序</title>
  </head>

  <body>
    <script>
      /*
       * 插入排序（insertion sort）思路：
       * 它将数组分成“已排序”和“未排序”两部分，一开始的时候，“已排序”的部分只有一个元素，
       * 然后将它后面一个元素从“未排序”部分插入“已排序”部分，从而“已排序”部分增加一个元素，
       * “未排序”部分减少一个元素。以此类推，完成全部排序。
       * 例如：数组[3, 2, 4, 1] 进行从小到大排序为例，步骤如下：
       * 1.将数组分成[3]和[2, 4, 1]]两部分，前者是已排序的，后者是未排序的。
       * 2.取出未排序部分的第一个元素“2”，与已排序部分最后一个元素“3”比较，
       *   因为2小于3，所以2排在3前面，整个数组变成[2, 3]和[4, 1]两部分。
       * 3.取出未排序部分的第一个元素“4”，与已排序部分最后一个元素“3”比较，
       *   因为4大于3，所以4排在3的后面，整个数组变成[2, 3, 4]和[1]两部分。
       * 4.取出未排序部分的第一个元素“1”，与已排序部分最后一个元素“4”比较，
       *   因为1小于4，所以再与前一个元素“3”比较；因为1小于3，再与前一个元素“2”比较；
       *   因为1小于2，所以“1”排在2的前面，整个数组变成[1, 2, 3, 4]。
       */
      var insertionArr = [3, 2, 4, 1];
      console.log("sortedArr=", insertionSort(insertionArr));

      function insertionSort(array) {
        let sortedArr = []; //已排序
        sortedArr.push(array[0]); //获取未排序数组中的第一个元素到已排序中
        //依次从未排序数组中取出元素，与已排序中的元素依次比较并插入到对应的位置上
        for (let i = 1; i < array.length; i++) {
          //已排序中从右向左依次比较
          for (let j = sortedArr.length - 1; j >= 0; j--) {
            //如果取出的元素比已排序中最后一个元素大，则插入到后面
            if (array[i] > sortedArr[j]) {
              sortedArr.splice(j + 1, 0, array[i]);
              break;
            }

            if (j == 0) {
              //如果新取出的元素是最小的，则直接放在最开始的位置
              sortedArr.unshift(array[i]);
            }
          }
        }
        return sortedArr;
      }
    </script>
  </body>
</html>
